from typing import List

class RLEIterator:
    def __init__(self, encoding: List[int]):
        self.vals = encoding[1::2]
        self.repeat = encoding[::2]
        self.index = [0, 0]

    def next(self, n: int) -> int:
        self.index[1] += n
        if self.index[0] >= len(self.repeat):
            return -1
        while self.repeat[self.index[0]] < self.index[1]:
            self.index[1] -= self.repeat[self.index[0]]
            self.index[0] += 1
            if self.index[0] >= len(self.repeat):
                return -1
        # print(self.index)
        return self.vals[self.index[0]]


if __name__ == '__main__':
    obj = RLEIterator([3, 8, 0, 9, 2, 5])
    print(obj.next(2))
    print(obj.next(1))
    print(obj.next(1))
    print(obj.next(2))
